package 二叉树.有序链表转换为二叉搜索树;



/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/6/1 20:31
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {

    }

    //基本思想和有序链表转二叉搜索树相同，不过这个实现起来更复杂一些
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode mid = getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    //找到链表的中间节点 快慢指针，找到链表的中间元素
    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        //这里就是保证fast先走到链表尾部
        while (fast != right && fast.next != right) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
